package com.xdja.sort;

public class FindMinK {
    public static void main(String[] args) {
        int[] data = new int[]{-4, 2, 10, 9, 8, 7, 6};
        System.out.println("最小值为:"+findMinK(data, 2));
    }

    public static int findMinK(int[] data, int k) {
        quickSort(data, 0, data.length - 1);
        return data[k];
    }

    public static void quickSort(int[] array, int left, int right) {
        if (left > right)
            return;
        int pivot = array[left];//定义基准值为数组第一个数
        int i = left;
        int j = right;

        while (i < j) {
            while (pivot <= array[j] && i < j)//从右往左找比基准值小的数,i < j 证明左边已经小于右边
                j--;
            while (pivot >= array[i] && i < j)//从左往右找比基准值大的数
                i++;
            if (i < j){//如果i<j，交换它们
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        array[left] = array[i];
        array[i] = pivot;//把基准值放到合适的位置
        quickSort(array, left, i - 1);//对左边的子数组进行快速排序
        quickSort(array, i + 1, right);//对右边的子数组进行快速排序
    }

}
